from typing import *


# 输入：s = "25525511135"
# 输出：["255.255.11.135","255.255.111.35"]
class Solution:

    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        n = len(s)

        def f(i=0):
            if i == n and len(arr) == 4:
                ans.append(".".join(arr))
                return
            if i == n or len(arr) == 4:
                return
            t = i + 2 if s[i] == '0' else n + 1
            for r in range(i + 1, t):
                if int(s[i:r]) <= 255:
                    arr.append(s[i:r])
                    f(r)
                    arr.pop()

        arr = []
        f()
        return ans


so = Solution()
# print(
#     so.restoreIpAddresses(
#         s="25525511135") == ["255.255.11.135", "255.255.111.35"])

print(so.restoreIpAddresses("0000") == ["0.0.0.0"])
print(so.restoreIpAddresses("1111") == ["1.1.1.1"])
print(so.restoreIpAddresses("010010") == ["0.10.0.10", "0.100.1.0"])
print(
    so.restoreIpAddresses(
        s="10203040") == ["10.20.30.40", "102.0.30.40", "10.203.0.40"])
